package cn.edu.jxau.test;

import java.util.Arrays;

public class Sort {

    public static void main(String[] args) {
        
        int[] arr = new int[10];
        for(int i=1;i<arr.length;i++) {
            arr[i] = (int)(Math.random()*100);
        }
        System.out.println(Arrays.toString(arr));
        sort(arr);
        System.out.println(Arrays.toString(arr));
    }

    private static void sort(int[] arr) {

        int size = arr.length - 1;
        for (int i = size / 2; i >= 1; i--) {
            sink(arr, i, size);
        }
        while (size > 1) {
            swap(arr, 1, size--);
            sink(arr, 1, size);
        }
    }

    private static void sink(int[] arr, int k, int size) {

        while (2 * k <= size) {
            int i = 2 * k;
            if (i < size && arr[i] < arr[i + 1]) {
                i++;
            }
            if (arr[k] >= arr[i])
                break;
            swap(arr, k, i);
            k = i;
        }
    }

    private static void swap(int[] arr, int i, int j) {

        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}
